#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define DU double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define rep(i,x,n) for(int i=(x);i<=(n);i++)
#define nep(i,x,n) for(int i=(x);i>=(n);i--)
using namespace std;
const int N=2010;
int n,a[N],f[N][N];
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
inline void print(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
inline void Solve(){
	n=read();rep(i,1,n) a[i]=read();
	if(n<=2000){
		rep(i,1,n){
			rep(j,0,i-2){
				f[i][j]=f[i-1][j]+(a[i]==a[i-1])*a[i];
				f[j][i]=f[j][i-1]+(a[i]==a[i-1])*a[i];
			}
			f[i][i-1]=f[i-1][i]=0;
			rep(j,0,i-2){
				f[i][i-1]=max(f[i][i-1],f[j][i-1]+(a[i]==a[j])*a[i]);
				f[i-1][i]=max(f[i-1][i],f[i-1][j]+(a[i]==a[j])*a[i]);
			}
		}
		int res=0;
		rep(i,0,n-1) res=max(res,max(f[n][i],f[i][n]));
		print(res),puts("");
		return ;
	}
	puts("-1");
}
int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	int Tests=read();
	while(Tests--) Solve();
	return 0;
}